package com.atguigui.leetcode1;

import java.util.Arrays;

/**
 * 1262. 可被三整除的最大和
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/6/19 13:35
 */
public class P1262GreatestSumDivisibleByThree {
    public static void main(String[] args) {
        Solution solution = new P1262GreatestSumDivisibleByThree().new Solution();
    }

    class Solution {
        public int maxSumDivThree(int[] nums) {
            int n = nums.length;
            var memo = new int[n][3];
            for (int i = 0; i < n; i++)
                Arrays.fill(memo[i], -1); // -1 表示没有计算过
            return dfs(memo, nums, n - 1, 0);
        }

        private int dfs(int[][] memo, int[] nums, int i, int j) {
            if (i < 0) return j == 0 ? 0 : Integer.MIN_VALUE;
            if (memo[i][j] != -1) return memo[i][j]; // 之前计算过
            return memo[i][j] = Math.max(dfs(memo, nums, i - 1, j), dfs(memo, nums, i - 1, (j + nums[i]) % 3) + nums[i]);
        }
    }


}
